import org.junit.jupiter.api.Test;

import java.util.Arrays;
import java.util.Map;
import java.util.stream.Collectors;

import static org.junit.Assert.assertEquals;
import static org.junit.jupiter.api.Assertions.assertNull;

public class Hash {
    @Test
    public void get() {
        HashTable table = new HashTable();
        HashTable.Entry e0 = new HashTable.Entry(0, "沙", "沙僧");
        e0.next = new HashTable.Entry(16, "于", "于谦");
        HashTable.Entry e1 = new HashTable.Entry(1, "空", "空见");

        table.table[0] = e0;
        table.table[1] = e1;

        assertEquals("沙僧", table.get(0, "沙"));
        assertEquals("于谦", table.get(16, "于"));
        assertNull(table.get(0, "空"));
        assertEquals("空见", table.get(1, "空"));
        assertNull(table.get(3, "空"));
    }


    @Test
    void put() {
        HashTable table = new HashTable();
        table.put(1, "zhang", "张三"); // 1 % 16 == 1
        table.put(17, "li", "李四");   // 17 % 16 == 1
        table.put(2, "wang", "王五");  // 2

        assertEquals(3, table.size);
        assertEquals("张三", table.table[1].value);
        assertEquals("李四", table.table[1].next.value);
        assertEquals("王五", table.table[2].value);

        table.put(1, "zhang", "张4");
        table.put(17, "li", "李5");
        assertEquals("张4", table.table[1].value);
        assertEquals("李5", table.table[1].next.value);
    }
    @Test
    void remove1() {
        HashTable table = new HashTable();
        table.put(1, "zhang", "张三");  // 1
        table.put(17, "li", "李四");    // 1
        table.put(2, "wang", "王五");

        table.remove(1, "zhang");
        assertEquals(2, table.size);
        assertEquals("李四", table.table[1].value);
        assertNull(table.table[1].next);
    }

    @Test
    void remove2() {
        HashTable table = new HashTable();
        table.put(1, "zhang", "张三"); // 1
        table.put(17, "li", "李四");   // 1
        table.put(2, "wang", "王五");

        table.remove(17, "li");
        assertEquals(2, table.size);
        assertEquals("张三", table.table[1].value);
        assertNull(table.table[1].next);
    }

    @Test
    void resize() {
        HashTable table = new HashTable();
        for (int i = 2; i < 11; i++) {
            table.put(i, new Object(), new Object());
        }
        table.put(1, "zhang", "张三"); // 原位不动
        table.put(17, "li", "李四");
        table.put(33, "wang", "王五"); // 原位不动
        assertEquals("张三", table.table[1].value);
        assertEquals("李四", table.table[1].next.value);
        assertEquals("王五", table.table[1].next.next.value);
        table.put(49, "zhao", "赵六");
        assertEquals(13, table.size);
        assertEquals(32, table.table.length);
        assertEquals(24, table.threshold);
        assertEquals("张三", table.table[1].value);
        assertEquals("王五", table.table[1].next.value);
        assertEquals("李四", table.table[17].value);
        assertEquals("赵六", table.table[17].next.value);
    }


}
class HashTable{
    //节点类
    static class Entry{
        int hash;
        Object key;
        Object value;
        Entry next;
        public Entry(int hash, Object key, Object value){
            this.hash = hash;
            this.key = key;
            this.value = value;
        }
    }

    /* 求模运算替换为位运算
        - 前提：数组长度是 2 的 n 次方
        - hash % 数组长度 等价于 hash & (数组长度-1)
     */
    Entry[] table = new Entry[16];
    int size = 0; // 元素个数
    float loadFactor = 0.75f; //负载因子,判断是否需要扩容  元素个数/数组长度  12 阈值
    int threshold = (int) (loadFactor * table.length);

    // 根据 hash 码获取 value
    Object get(int hash, Object key){
        int idx = hash & (table.length - 1);
        if (table[idx] == null){
            return null;
        }
        Entry p = table[idx];
        while (p != null){
            if (p.key.equals(key)){
                return p.value;
            }
            p = p.next;
        }
        return null;
    }


    // 向 hash 表存入新 key value，如果 key 重复，则更新 value
    void put(int hash, Object key, Object value){
        int idx = hash & (table.length - 1);
        if (table[idx] == null){
            // 1. idx 处有空位, 直接新增
            table[idx] = new Entry(hash, key, value);
        }else {
            // 2. idx 处无空位, 沿链表查找 有重复key更新，否则新增
            Entry p = table[idx];
            while (true){
                if (p.key.equals(key)){
                    p.value = value;
                    return;
                }
                if (p.next == null){
                    break;
                }
                p = p.next;
            }
            p.next = new Entry(hash, key, value);
        }
        size++;
        if (size > threshold){
            resize();
        }
    }

    //扩容
    private void resize(){
        Entry[] newTable = new Entry[table.length << 1];
        for (int i = 0; i < table.length; i++){
            // 拿到每个链表头
            Entry p = table[i];
            if (p != null){
                /*
                拆分链表，移动到新数组，拆分规律
                * 一个链表最多拆成两个
                * hash & table.length == 0 的一组
                * hash & table.length != 0 的一组
                                          p
                0->8->16->24->32->40->48->null
                            a
                0->16->32->48->null
                        b
                8->24->40->null
             */
                Entry a = null;
                Entry b = null;
                Entry aHead = null;
                Entry bHead = null;
                while (p != null){
                    if ((p.hash & table.length) == 0){
                        if (a != null){
                            a.next = p;
                        }else {
                            aHead = p;
                        }
                        //分配给a
                        a = p;
                    }else {
                        if (b != null){
                            b.next = p;
                        }else {
                            bHead = p;
                        }
                        //分配给b
                        b = p;
                    }
                    p = p.next;
                }
                // 规律： a 链表保持索引位置不变，b 链表索引位置+table.length
                if (a != null){
                    a.next = null;
                    newTable[i] = aHead;
                }
                if (b != null){
                    b.next = null;
                    newTable[i + table.length] = bHead;
                }
            }
        }
        table = newTable;
        threshold = (int) (loadFactor * table.length);
    }

    // 根据 hash 码删除，返回删除的 value
    Object remove(int hash, Object key){
        int idx = hash & (table.length - 1);
        if (table[idx] == null){
            return null;
        }
        Entry p = table[idx];
        Entry prev = null;
        while (p != null){
            if (p.key.equals(key)){
                //找到了
                if (prev == null){// 链表头
                    table[idx] = p.next;
                }else {// 非链表头
                    prev.next = p.next;
                }
                size--;
                return p.value;
            }
            prev = p;
            p = p.next;
        }
        return null;
    }

    public Object get(Object key){
        return get(key.hashCode(), key);
    }

    public void put(Object key, Object value){
        put(key.hashCode(), key, value);
    }

    public Object remove(Object key){
        return remove(key.hashCode(), key);
    }

    public static void main(String[] args) {
        // 原则：值相同的字符串生成相同的 hash 码, 尽量让值不同的字符串生成不同的 hash 码
    /*
    对于 abc  a * 100 + b * 10 + c
    对于 bac  b * 100 + a * 10 + c
     */
        String s1 = "bac";
        String s2 = new String("abc");
        int hash = 0;

//        System.out.println(s1.hashCode());
//        System.out.println(s2.hashCode());

        for (int i = 0; i < s1.length(); i++){
            char c = s1.charAt(i);
            hash = ((hash << 5) - hash) + c;
            System.out.println(hash);
        }
    }

    //检查hash表的分散性
    @Test
    public void print() {
        int[] sum = new int[table.length];
        for (int i = 0; i < table.length; i++) {
            Entry p = table[i];
            while (p != null) {
                sum[i]++;
                p = p.next;
            }
        }
        System.out.println(Arrays.toString(sum));

        Map<Integer, Long> result = Arrays.stream(sum).boxed()
                .collect(Collectors.groupingBy(s -> s, Collectors.counting()));
        System.out.println(result);
    }

}
